﻿#include "LR1Parsers.h"
#include "LanguageAlgorithm.h"
#include <fstream>
#include <cctype>
#include <cassert>
#include <WllTrace.h>
#include "WllUtil.h"
#include <string.h>
#include <CompilerManager.h>
#include "WllSingleton.h"

using namespace std;
using namespace Wll::Util;

//判定文法是否存在移近规约冲突（文法二义性判断）
bool LR1Parsers::IsAmbiguous(const vector< vector< TransformEdge > >& state_transform_table, const vector< StateSets<LR1States> >& state_sets)
{
	assert(state_transform_table.size() == state_sets.size());

	bool flag = false;
	int n = 0;
	for(vector< vector< TransformEdge > >::const_iterator i = state_transform_table.begin(); i != state_transform_table.end(); ++i)
	{
		map<Symbols,int> stat_map;
		for(vector<TransformEdge>::const_iterator j = i->begin(); j != i->end(); ++j)
		{
			Symbols symbol = j->symbol;
			if(stat_map.find(symbol)==stat_map.end())
				stat_map[symbol]=1;
			else
				stat_map[symbol]++;
		}

		//check & output conflict
		if(stat_map.size() != i->size())
		{
			flag = true;
			//#ifdef	DEBUG
			cerr<<"conflict in state transform table (state no = "<<n<<") :"<<endl;
			//cerr<<state_sets[n]<<endl;

			for(map<Symbols,int>::iterator it = stat_map.begin(); it != stat_map.end(); ++it)
			{
				if(it->second > 1)	//conflict item
				{
					cerr<<"conflict Symbol: "; it->first.Dump(cerr); cerr<<endl;
					for(set<LR1States>::const_iterator k=state_sets[n].states.begin(); k!=state_sets[n].states.end(); ++k)
					{
						if(k->IsReduceState())
						{
							if(k->follow.find(it->first)!=k->follow.end())
							{
								cerr<<"reduce state "<<n<<": "; cerr<<*k<<endl;
							}
						}
						else if(it->first == k->rule->expression.symbols[k->position])
						{
							cerr<<"move state "<<n<<": "; cerr<<*k<<endl;
						}
					}
					cerr<<"+++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
				}
			}
			//#endif	//DEBUG 
		}

		++n;
	}
	return flag;
}

bool LR1Parsers::Initialize()
{
    if (this->isInitialized)
    {
        INFO("already initialized");
        return true;
    }
    INFO("not initialized, try to initialize LR1Parser");

    INFO("GenerateStateTransformTable start ...");
    //根据文法自动生成文法预测分析表
    vector< vector<TransformEdge> > state_transform_table;
    GenerateStateTransformTable(this->languages.source_rules,state_transform_table,this->state_sets, this->entries);
    if(this->IsAmbiguous(state_transform_table, this->state_sets)) return false;
    INFO("GenerateStateTransformTable end success");

    INFO("ConvertStateTransformTable start ...");
    this->state_transform_table.clear();
    ConvertStateTransformTable(state_transform_table,this->state_transform_table);
    DEBUG_LOG("state_transform_table=\n"<<this->state_transform_table);
    INFO("ConvertStateTransformTable end success");

    this->isInitialized = true;
    return true;
}

//根据文法规则对输入符号流进行文法结构的分析,分析结果用文法分析树表示
bool LR1Parsers::Parse(SymbolsFlow& input_symbols, LanguageTree*& source_tree, Symbols start_symbol)
{
    if (!this->Initialize()) return false;
	INFO("LRParse start ...");
	//根据文法预测分析表分析文法,得到文法分析树
  	bool retval = LRParse(start_symbol, input_symbols, source_tree, this->state_transform_table,
                          this->languages.source_rules.rules, this->state_sets, this->entries);
    if (retval)
    {
        INFO("LRParse end success");
    }
    else
    {
        INFO("LRParse end failed");
    }
	
	return retval;
}

void LR1Parsers::DisplayStates()
{
	int n = 0;
	for(vector< StateSets<LR1States> >::const_iterator i = this->state_sets.begin(); i != this->state_sets.end(); ++i)
	{
		cout<<"State "<<n<<" : "<<*i<<endl;
		++n;
	}
}

//保存语法分析器状态到文件
bool LR1Parsers::Save(ostream& o)
{
    //INFO("save states");
    //SaveStates(o);
    INFO("save transform table");
    SaveTransformTable(o);
    INFO("save entries");
    SaveEntries(o);
    INFO("save lr1 parser completed");
}

//从文件加载语法分析器状态
bool LR1Parsers::Load(istream& i)
{
    //INFO("load states");
    //LoadStates(i);
    INFO("load tranform table");
    LoadTransformTable(i);
    INFO("load entries");
    LoadEntries(i);
    INFO("load lr1 parser completed");

    this->isInitialized = true;
    return true;
}

void LR1Parsers::SaveStates(ostream &o) {
    size_t state_sets_size = state_sets.size();
    o.write(reinterpret_cast<const char *>(&state_sets_size), sizeof(state_sets_size));
    for (vector< StateSets<LR1States> >::iterator i = state_sets.begin(); i != state_sets.end(); ++i)
    {
        size_t set_size = i->states.size();
        o.write(reinterpret_cast<const char *>(&set_size), sizeof(set_size));
        for (set<LR1States>::iterator j = i->states.begin(); j != i->states.end(); ++j)
        {
            j->Save(o);
        }
    }
}

void LR1Parsers::LoadStates(istream &i) {
    state_sets.clear();
    size_t state_sets_size = 0;
    i.read(reinterpret_cast<char *>(&state_sets_size), sizeof(state_sets_size));
    for (int j = 0; j < state_sets_size; j++)
    {
        StateSets<LR1States> state_set;
        size_t set_size = 0;
        i.read(reinterpret_cast<char *>(&set_size), sizeof(set_size));
        for (int k = 0; k < set_size; k++)
        {
            LR1States lr1States;
            lr1States.Load(i);
            lr1States.rule = languages.source_rules.GetRule(lr1States.rule_no);
            state_set.states.insert(lr1States);
        }
        state_sets.push_back(state_set);
    }
}

void LR1Parsers::SaveTransformTable(ostream& o) {
    size_t size = state_transform_table.size();
    o.write(reinterpret_cast<const char *>(&size), sizeof(size));
    for (int i = 0; i < size; i++)
    {
        size_t map_size = state_transform_table[i].size();
        o.write(reinterpret_cast<const char *>(&map_size), sizeof(map_size));
        for (map<Symbols, Actions>::iterator j = state_transform_table[i].begin(); j != state_transform_table[i].end(); ++j)
        {
            j->first.Save(o);
            j->second.Save(o);
        }
    }
}

void LR1Parsers::LoadTransformTable(istream &i) {
    state_transform_table.clear();
    size_t size = 0;
    i.read(reinterpret_cast<char *>(&size), sizeof(size));
    for (int j = 0; j < size; j++)
    {
        size_t map_size = 0;
        map<Symbols, Actions> m;
        i.read(reinterpret_cast<char *>(&map_size), sizeof(map_size));
        for (int k = 0; k < map_size; k++)
        {
            Symbols s;
            s.Load(i);
            Actions a;
            a.Load(i);
            if (a.type == REDUCE_ACTION)
            {
                a.rule = languages.source_rules.GetRule(a.value);
            }
            else if (a.type == MOVE_ACTION)
            {
                a.state = &state_sets[a.value];
            }
            m.insert(make_pair(s,a));
        }
        state_transform_table.push_back(m);
    }
}

void LR1Parsers::SaveEntries(ostream &o) {
    size_t entries_size = entries.size();
    o.write(reinterpret_cast<const char *>(&entries_size), sizeof(entries_size));
    for (map<Symbols, size_t>::iterator i = entries.begin(); i != entries.end(); ++i)
    {
        i->first.Save(o);
        o.write(reinterpret_cast<const char *>(&i->second), sizeof(i->second));
    }
}

void LR1Parsers::LoadEntries(istream &i) {
    entries.clear();
    size_t entries_size = 0;
    i.read(reinterpret_cast<char *>(&entries_size), sizeof(entries_size));
    for (int j = 0; j < entries_size; j++)
    {
        Symbols s;
        s.Load(i);
        size_t entry;
        i.read(reinterpret_cast<char *>(&entry), sizeof(entry));
        entries.insert(make_pair(s, entry));
    }
}
